TNotes.leetcode

Appearance

0507. 完美数【简单】

0507. 完美数【简单】 ​

1. 📝 题目描述 ​

对于一个 正整数，如果它和除了它自身以外的所有 正因子 之和相等，我们称它为 「完美数」。

给定一个 整数 n， 如果是完美数，返回 true；否则返回 false。

示例 1：

txt
输入：num = 28
输出：true
解释：28 = 1 + 2 + 4 + 7 + 14
1, 2, 4, 7, 和 14 是 28 的所有正因子。

示例 2：

txt
输入：num = 7
输出：false

提示：

  • 1 <= num <= 10^8

2. 🎯 s.1 - 暴力解法 ​

js
/**
 * @param {number} num
 * @return {boolean}
 */
var checkPerfectNumber = function (num) {
  // 1 不是完美数
  if (num <= 1) {
    return false
  }

  let sum = 1 // 1 是所有大于1的数的因子

  // 只需要检查到 sqrt(num)
  for (let i = 2; i * i <= num; i++) {
    if (num % i === 0) {
      sum += i
      // 如果 i 不是平方根，则 num/i 也是因子
      if (i * i !== num) {
        sum += num / i
      }
    }
  }

  return sum === num
}
  • 时间复杂度：O(n)，只需要遍历到 num
  • 空间复杂度：O(1)，只使用了常数级别的额外空间
  • 算法思路：
    1. 边界处理：
      • 如果 num <= 1，直接返回 false，因为 1 不是完美数
    2. 初始化因子和：
      • sum 初始化为 1，因为 1 是所有大于 1 的正整数的因子
    3. 查找因子：
      • 从 2 开始遍历到 sqrt(num)
      • 如果 i 是 num 的因子，则 num/i 也是因子
      • 避免重复计算平方根的情况
    4. 结果判断：
      • 比较所有因子之和是否等于原数
  • 执行过程示例：
txt
28 的正因子：1, 2, 4, 7, 14, 28
除自身外的因子和：1 + 2 + 4 + 7 + 14 = 28

查找过程：
i = 2: 28 % 2 = 0，2 和 28/2=14 都是因子，sum = 1 + 2 + 14 = 17
i = 3: 28 % 3 ≠ 0，不是因子
i = 4: 28 % 4 = 0，4 和 28/4=7 都是因子，sum = 17 + 4 + 7 = 28
i = 5: 5*5 = 25 ≤ 28，但 28 % 5 ≠ 0，不是因子
i = 6: 6*6 = 36 > 28，循环结束

sum = 28，等于原数，返回 true
txt
7 的正因子：1, 7
除自身外的因子和：1

查找过程：
i = 2: 2*2 = 4 ≤ 7，但 7 % 2 ≠ 0，不是因子
i = 3: 3*3 = 9 > 7，循环结束

sum = 1，不等于原数，返回 false

3. 🎯 s.2 - 预计算 ​

js
/**
 * @param {number} num
 * @return {boolean}
 */
var checkPerfectNumber = function (num) {
  // 在 32 位整数范围内，已知的完美数只有这几个
  return (
    num === 6 || num === 28 || num === 496 || num === 8128 || num === 33550336
  )
}
  • 时间复杂度：O(1)，仅执行固定次数的比较操作
  • 空间复杂度：O(1)，使用常量级额外空间
  • img
  • 算法思路：
    • 题目限制了输入范围：1 <= num <= 10^8，这一点可以从提示中得知。
    • 最大输入 108 还没超出 32 位有符号整数（2,147,483,647） 的范围。
    • 在这个范围内，数学上已经证明：唯一的完美数就是 6, 28, 496, 8128, 33550336。
      • 下一个完美数是 8,589,869,056，已经超过 108。
      • 所以，只需要枚举这几个就行，复杂度 O(1)，能直接通过。
  • 在 JS 里，数值类型是 64 位双精度浮点数（IEEE 754）。
    • 可安全表示的整数范围：-(2^53 - 1) 到 2^53 - 1（约 ±9e15）。
    • JS 支持大于 32 位的整数，但 LeetCode 这道题本身 只考察 108 以内的数，所以你根本不用考虑 32 位还是 64 位的问题。

Discussions